package 根据数据量猜解法的技巧_天字第一号技巧;


import java.io.*;

// 测试链接 : https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"
// 可以直接通过
public class Code01_KillMonsterEverySkillUseOnce {

    // 技能数 <= 10
    public static int MAXN = 11;
    // 每个技能的伤害值
    public static int[] kill = new int[MAXN];
    // 使用这个技能时，当血量小于blood[i]的值时，kill[i]造成的伤害双倍
    public static int[] blood = new int[MAXN];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF){
            // 测试数据组
            int t = (int) in.nval;
            for(int i = 0; i < t; i++){
                in.nextToken();
                // 技能数
                int n = (int) in.nval;
                in.nextToken();
                // 血量
                int m = (int) in.nval;
                for(int j = 0; j < n; j++){
                    in.nextToken();
                    // 每个技能的单倍伤害
                    kill[j] = (int) in.nval;
                    in.nextToken();
                    // 每个技能多少血量能出发双倍伤害
                    blood[j] = (int) in.nval;
                }
                // 技能编号i从0开始
                int ans = f(n, 0, m);
                out.println(ans == Integer.MAX_VALUE ? -1 : ans);
            }
        }
        out.flush();
        br.close();
        out.close();
    }

    // kill[i]、blood[i]
    // n : 一共几个技能
    // i : 当前来到了第几号技能
    // r : 怪兽目前的剩余血量
    public static int f(int n, int i, int r){
        if(r <= 0){
            // 之前的决策已经让怪兽挂了！返回使用了多少个节能
            return i;
        }
        // r > 0
        if(i == n){
            // 技能用完了，怪兽血量还有剩余，之前的技能决策无效，之前的决策无效
            return Integer.MAX_VALUE;
        }
        // 返回至少需要几个技能可以将怪兽杀死
        int ans = Integer.MAX_VALUE;
        for(int j = i; j < n; j++){
            swap(i, j);
            ans = Math.min(ans, f(n, i+1, r - (r > blood[i] ? kill[i] : kill[i]*2)));
            swap(i, j);
        }
        return ans;
    }

    // i号技能和j号技能，参数交换
    // j号技能要来到i位置，试一下
    public static void swap(int i, int j){
        int tmp = kill[i];
        kill[i] = kill[j];
        kill[j] = tmp;
        tmp = blood[i];
        blood[i] = blood[j];
        blood[j] = tmp;
    }
}
